Large networks like the Internet, enterprise networks, metropolitan area networks, and cellular networks transport information using packets that are routed and switched through various segments of a network. Within these networks, users are provided with a plurality of user applications. User applications are becoming increasingly more complex, and the amount of data generated by these applications is increasing at an exponential rate. To accommodate user demand for data intensive applications, only two options exist. The first option entails increasing the capacity of existing networks, by adding more equipment to the infrastructure. This approach is not only expensive, but it also requires a significant amount of network downtime in order to properly install and troubleshoot the addition of new hardware and software to existing network infrastructure. The second option includes developing techniques to optimize the performance of the existing infrastructure.
Several traffic control techniques have been implemented to address this problem. The most rudimentary traffic control technique discards packets if the network is congested. More advanced techniques, including Transmission Control Protocol (TCP), and several variants of TCP use a sliding window that limits the total number of unacknowledged packets in transit from end-to-end. TCP, however, treats all network packets the same, which can result in an increase in the number of dropped packets as the number of connections increases. Each connection established between devices represents a connection established by an individual application. For example, a user might be downloading a software update for a word processor, using an email client, using a web browser, hosting a website, streaming multimedia (e.g. video or audio), using an instant messaging program, running a virtual desktop program, etc. In this scenario, it is possible that eight or more different connections are formed. In a virtual environment, however, a single machine can host applications for multiple users utilizing the same services. This results in a significant increase in the total volume of data, and the number of connections needed to support the required bandwidth of each application requesting access to the Internet. To ensure packets are not discarded, and each connection is given an equal opportunity to transmit the packets in their queue, techniques for scheduling a number of packets, and a number of connections used to transmit packets on a given connection must be developed.
A packet scheduler can be used to ensure that packets are not discarded and each connection is given an opportunity to transmit packets that are in their queues. The packet scheduler accomplishes this by prioritizing packets on each connection. For example, VoIP data or video data might not be as tolerable to latency as email and web data. As a result the packet scheduler can assign a higher priority to packets associated with VoIP or video data than packets associated with email or web data, to ensure that VoIP or video data packets are not dropped.
But in typical packet-scheduling systems, the prioritizing of packets is not an efficient process, especially when the prioritizing is across a large number of connections (e.g., in some cases, hundreds or thousands of connections). An alternative approach has been created that provides a more efficient prioritizing process for a packet scheduler organizing and managing a large number of connections.